package Leetcode.数组字符串;

/**
 * @ClassName 字符串的最大公因子
 * @since: 2023/8/3 16:52
 * @auth: kirito
 * @description:
 * 对于字符串 s 和 t，只有在 s = t + ... + t（t 自身连接 1 次或多次）时，
 * 我们才认定 “t 能除尽 s”。
 *
 * 给定两个字符串 str1 和 str2 。返回 最长字符串 x，
 * 要求满足 x 能除尽 str1 且 x 能除尽 str2 。
 *
 * 输入：str1 = "ABCABC", str2 = "ABC"
 * 输出："ABC"
 * 示例 2：
 *
 * 输入：str1 = "ABABAB", str2 = "ABAB"
 * 输出："AB"
 **/
public class 字符串的最大公因子 {
    public static String gcdOfStrings(String str1, String str2) {
        int len1 = str1.length(), len2 = str2.length();
        for (int i = Math.min(len1, len2); i >= 1; --i) { // 从长度大的开始枚举
            if (len1 % i == 0 && len2 % i == 0) {
                //因为是最大，则先最长开始取
                // 取短的字符串的全部  如果是最大，则返回，否然后慢慢取少一点
                String X = str1.substring(0, i);
                if (check(X, str1) && check(X, str2)) {  //然后判断是否取得的这个字符串是都是每个父字符串的公因子
                    return X;
                }
            }
        }
        return "";
    }

    public static boolean check(String t, String s) {
        //复制lenx份公因子  如果equals，则返回公因子X  这个应该好理解
        int lenx = s.length() / t.length();
        StringBuffer ans = new StringBuffer();
        for (int i = 1; i <= lenx; ++i) {
            ans.append(t);
        }
        return ans.toString().equals(s);
    }
}
